Króliki

Limit pamięci: 256 MB

Bajtazar postanowił zacząć żyć ekologicznie, i został hodowcą sałaty. Jak wiadomo, bajtockie króliki uwielbiają sałatę, nic więc dziwnego, że wkrótce zawitały one do ogródka Bajtazara.

Wokół domu Bajtazara rozmieszczone jest grządek sałaty, które będziemy numerować od do . Każde dwie kolejne grządki sąsiadują ze sobą, tzn. dla każdego grządki o numerach oraz sąsiadują ze sobą. Dodatkowo, grządka o numerze sąsiaduje z grządką o numerze . Na grządce o numerze siedzi królików i pałaszuje sałatę Bajtazara.

Bajtazar chciałby przegonić z ogródka jak najwięcej królików. Ma do dyspozycji swoją starą, wierną strzelbę, w której jest nabojów. Króliki są bardzo płochliwe, więc gdy tylko Bajtazar wystrzeli w kierunku grządki o numerze , to wszystkie króliki z tej grządki uciekają w siną dal. Co więcej, przestraszone króliki z obu sąsiednich grządek przeskakują na dalsze grządki, tzn. kicają na grządkę sąsiadującą z tą, na której stoją - oczywiście nie tą, w kierunku której strzelał Bajtazar.

Pomóż Bajtazarowi i wyznacz maksymalną liczbę królików, które może on wygonić z ogródka za pomocą co najwyżej strzałów.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (, ), oznaczające liczbę grządek w ogródku i liczbę nabojów w strzelbie Bajtazara. W drugim wierszu znajduje się ciąg liczb całkowitych (), które oznaczają liczby królików na kolejnych grządkach.

Wyjście

Na wyjście należy wypisać jedną liczbę całkowitą - maksymalną liczbę królików, które Bajtazar jest w stanie przegonić z ogródka.

Przykład

Dla danych wejściowych:

5 2
6 1 5 3 4

poprawną odpowiedzią jest:

13

Wyjaśnienie do przykładu: Bajtazar przegania 6 królików z grządki numer 1 (wskutek czego króliki z grządki numer 5 przeskakują na grządkę numer 4, zaś króliki z grządki numer 2 przeskakują na grządkę numer 3), a następnie przegania 7 królików z grządki numer 4.

Autor zadania: Tomasz Idziaszek.